package com.study.dataStructure.tree;

import lombok.Data;
import lombok.ToString;

/**
 * @author tiny
 * @date 2021/11/11 22:25
 * @Description: 二叉树的结点
 */
@Data
@ToString
public class HeroNode {

    Integer no;
    String name;
    HeroNode left;
    HeroNode right;

    public HeroNode(Integer no,String name){
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString(){
        return String.format("Hero [no=%d, name=%s]",no,name);
    }

    /**
     * 前序遍历(根左右)
     */
    public void preList(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preList();
        }
        if(this.right!=null){
            this.right.preList();
        }
    }

    /**
     * 中序遍历（左根右）
     */
    public void infixList(){
        if(this.left!=null){
            this.left.infixList();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixList();
        }
    }

    /**
     * 后序遍历(左右根)
     */
    public void postList(){
        if(this.left!=null){
            this.left.postList();
        }
        if(this.right!=null){
            this.right.postList();
        }
        System.out.println(this);

    }

    /**
     * 前序查找
     * @param no
     * @return
     */
    public HeroNode preSearch(int no) {
        System.out.println(this.no);
        if(this.no == no) return this;
        HeroNode temp = null;
        if(this.getLeft()!=null){
            temp = this.getLeft().preSearch(no);
        }
        if(temp != null) return temp;
        if(this.getRight()!=null){
            temp = this.getRight().preSearch(no);
        }
        return temp;
    }

    /**
     * 中序查找
     * @param no
     * @return
     */
    public HeroNode infixSearch(int no) {
        HeroNode temp = null;
        if(this.getLeft() != null){
            if(this.getLeft().no == no)return this.getLeft();
            temp = this.getLeft().infixSearch(no);
        }
        if(temp!=null) return temp;
        if(this.no == no) return this;
        if(this.getRight()!=null){
            if(this.getRight().no==no) return this.getRight();
            temp = this.getRight().infixSearch(no);
        }
        return temp;
    }

    /**
     * 后序查找
     * @param no
     * @return
     */
    public HeroNode postSearch(int no) {
        HeroNode temp = null;
        if(this.getLeft() != null){
            if(this.getLeft().no == no) return this.getLeft();
            temp = this.getLeft().postSearch(no);
            if(temp!=null) return temp;
        }

        if(this.getRight()!=null){
            if(this.getRight().no == no) return this.getRight();
            temp = this.getRight().postSearch(no);
            if(temp!=null) return temp;
        }

        return temp;
    }

    /**
     * 删除结点
     * 单向二叉树，无法获取父结点，因而只能删除子节点
     */
    public HeroNode delNode(int no){
        //先找左子结点,再找右子结点
        //因为是单向二叉树,找不到父结点,只能删除子结点
        if(this.left!=null && this.left.no == no){
            HeroNode leftTemp = this.left;
            this.left = null;
            return leftTemp;
        }

        if(this.right!=null && this.right.no == no){
            HeroNode rightTemp = this.right;
            this.right = null;
            return rightTemp;
        }

        if(this.left!=null){
            return this.left.delNode(no);
        }

        if(this.right!=null){
            return this.right.delNode(no);
        }

       return null;
    }

    /**
     * 如果目标删除的结点不是叶子结点,只删除该结点而不删除以该结点为根结点的子树
     * @param no
     * @return
     */
    public HeroNode delNode2(int no){

        if(this.left!=null && this.left.no == no){
            HeroNode leftTemp = this.left;
            if(this.left.left==null && this.left.right==null){
                this.left = null;
            }else
            if( leftTemp.left!=null ){
                this.left = this.left.left;
            }
            if( leftTemp.right!=null ){
                this.left.right = leftTemp.right;
            }
            return leftTemp;
        }

        if(this.right!=null && this.right.no == no){
            HeroNode rightTemp = this.right;
            if(this.right.left==null && this.right.right==null){
                this.right = null;
            }else
            if( rightTemp.left!=null ){
                this.right = this.right.left;
            }
            if( rightTemp.right!=null ){
                this.right.right = rightTemp.right;
            }
            return rightTemp;
        }

        if(this.left!=null){
            return this.left.delNode2(no);
        }

        if(this.right!=null){
            return this.right.delNode2(no);
        }

        return null;
    }


}
